package com.practice.bit;

import java.util.HashMap;

public class RomanNumeral {
	private final static String[] ROMAN = new String[]{
		"I", "V", "X", "L", "C", "D", "M",
		"I^", "V^", "X^", "L^", "C^", "D^", "M^"};
	
	public String numberToRoman(int n) {
		StringBuilder builder = new StringBuilder();
		char[] c = ("" + n).toCharArray();
		int N = c.length;
		
		for (int i=0; i<N; i++) {
			int bit = N - i;
			if (c[i] > '0' && c[i] < '4') {
				for (int j=0; j<c[i]-'0'; j++) builder.append(ROMAN[2*bit-2]);
			}
			else if (c[i] == '4') {
				builder.append(ROMAN[2*bit-2]);
				builder.append(ROMAN[2*bit-1]);
			}
			else if (c[i] == '5') {
				builder.append(ROMAN[2*bit-1]);
			}
			else if (c[i] > '5' && c[i] < '9') {
				builder.append(ROMAN[2*bit-1]);
				for (int j=0; j<c[i]-'5'; j++) builder.append(ROMAN[2*bit-2]);
			}
			else if (c[i] == '9') {
				builder.append(ROMAN[2*bit-2]);
				builder.append(ROMAN[2*bit]);
			}
		}
		
		return builder.toString();
	}
	
	public int romanToNumber(String s) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for (int i=0, base=1; i<ROMAN.length/2; i++, base*=10) {
			map.put(ROMAN[2*i], base);
			map.put(ROMAN[2*i+1], 5*base);
		}
		
		int prev = 1;
		int n = 0;
		for (int i=s.length()-1; i>=0; i--) {
			int t = map.get(s.charAt(i) + "");
			if (t >= prev) {
				n += t;
				prev = t;
			}
			else {
				n -= t;
			}
		}
		
		return n;
	}
}
